package leetcode;

/**
 * Created by baoyunfeng on 2019/8/6.
 * <p>
 * 思路1：递归，对已知解给出答案，对未知解进行递归，回归到已知问题解决。判断过多。。。记不住。GG
 * 思路2：
 */
public class Regular_Expression_Matching2 {

    public static void main(String args[]) {
        isMatch("abbbbbcdef", "ab*cdef");
    }

    public static boolean isMatch(String a, String b) {
        boolean[][] dp = new boolean[a.length()+1][b.length()+1];

        dp[0][0] =  true;

        for(int i = 1 ; i<a.length() ;i++){
            for(int j = 1; j<b.length();j++) {
                if(b.charAt(j-2) == '*'){
                    dp[i][j] = dp[i][j - 2] || dp[i-1][j] && (a.charAt(i-1) == b.charAt(j-2));
                }else{
                    dp[i][j] = dp[i - 1][j - 1] && (a.charAt(i - 1) == b.charAt(j - 1) || b.charAt(j - 1) == '.');
                }
            }
        }

        return dp[a.length()][b.length()];
    }
}
